package com.company.nowcoder;

public class 牛能和牛可乐的礼物 {

    public int maxPresent (int[] presentVec) {
        // write code here
        int sum = 0;
        for (int i = 0; i < presentVec.length; i++) {
            sum += presentVec[i];
        }

        int[] dp = new int[sum / 2 + 1];

        for (int i = 0; i < presentVec.length; i++) {
            for (int j = sum/2; j >= presentVec[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - presentVec[i]] + presentVec[i]);
            }
        }

        return sum - dp[sum / 2] * 2;
    }

}
